9.1 KB · ⇊ 3 parts · ⤓ Micron 9.1 KB · ⤓ HTML 26.3 KB

layout: Wide · Narrow · Centered

top

Andrew Chi-Chih Yao (chinois : 姚期智; pinyin : Yáo Qīzhì), né à Shanghai le 24 décembre 1946, est un chercheur en informatique. Il a reçu le prix Knuth en 1996 et le prix Turing en 2000.

• Biographie

• Travaux

• Distinctions

• Notes et références

• Liens externes

Andrew Yao est né à Shanghai le 24 décembre 1946. Il a vécu ses premières années à Hong Kong puis à Taïwancite-ref-turing-1-0[1].

Il a fait son premier cycle universitaire en physique à l'université nationale de Taïwan. Il a obtenu un doctorat en physique de l'université Harvard en 1972, sous la direction de Sheldon Glashowcite-ref-knuth-2-0[2] et en informatique de l'université de l'Illinois à Urbana-Champaign en 1975, sous la direction de Chung Laung Liucite-ref-3[3].

Il a travaillé au MIT à l'université de Californie à Berkeley et à l'université Stanford avant d'être professeur à l'université de Princetoncite-ref-knuth-2-1[2] et à l'université Tsinghua.

De façon générale, il a fait avancer de très nombreux domaines de l'informatique théoriquecite-ref-knuth-2-2[2].

En cryptographie et en sécurité, on lui doit par exemple modèle de Dolev-Yao (en) et le problème du millionnaire (en).

En algorithmique plus classique, il a été le premier à utiliser l'algorithme minimax pour prouver ce que l'on nomme le principe de Yao, un outil permettant d'étudier les algorithmes probabilistes. Il a aussi travaillé sur les structures de données, en utilisant notamment la théorie de Ramsey dans l'article Should Tables Be Sortedcite-ref-4[4]. Il a amélioré la complexité en temps de la recherche d'un arbre couvrant de poids minimalcite-ref-knuth-2-3[2]cite-ref-5[5].

Il a aussi jeté les bases de la complexité de la communicationcite-ref-knuth-2-4[2], dans l'article Some Complexity Questions Related to Distributed Computingcite-ref-6[6], et travaillé sur les circuits booléens.

Après le prix Knuth en 1996cite-ref-knuth-2-5[2], il a reçu le prix Turing en 2000 pour ses contributions en théorie de la calculabilité, génération de nombres pseudo-aléatoires, cryptographie et complexité de la communicationcite-ref-turing-1-1[1].

Il reçoit le prix de Kyoto en 2021cite-ref-7[7].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Andrew Yao » (voir la liste des auteurs).

cite-note-turing-11. « Andrew Chi-Chih Yao », sur Association for Computing Machinery.

cite-note-knuth-22. 1996« Laudatio du prix Knuth 1996 », sur SIGACT, 1996.

cite-note-33. ↑ (en) « Andrew Yao », sur le site du Mathematics Genealogy Project

cite-note-44. ↑ chi-chih-yao1981andrew-chi-chih-yao1981Andrew Chi-Chih Yao, « Should Tables Be Sorted? », J. ACM, vol. 28, no 3,‎ 1981, p. 615-628

cite-note-55. ↑ chi-chih-yao1975andrew-chi-chih-yao1975Andrew Chi-Chih Yao, « An O(E log log V) Algorithm for Finding Minimum Spanning Trees », Inf. Process. Lett., vol. 4, no 1,‎ 1975, p. 21-23

cite-note-66. ↑ yao1979andrew-chi-chih-yao1979Andrew Chi-Chih Yao, « Some complexity questions related to distributive computing », dans Proceedings of the eleventh annual ACM symposium on Theory of computing, 1979, p. 209-213

cite-note-77. ↑ 2021(en) « The 2021 Kyoto Prize Laureates Announced! », 18 juin 2021

• site-officiel(en) Site officiel

• Ressources relatives à la recherche : Digital Bibliography & Library Project Mathematics Genealogy Project Scopus

• Notice dans un dictionnaire ou une encyclopédie généraliste : Britannica

• Notices d'autorité : VIAF ISNI LCCN Australie

• (en) Page personnelle

• (en) Biographie d'Andrew Yao

• Portail de la cryptologie

• Portail de l'informatique théorique

• Portail de la Chine